package BinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-22
 * Time: 10:59
 */

import java.util.Stack;

/**
 * 二叉树的最近公共祖先:

 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出：3
 * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 * 示例 2：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出：5
 * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 * 示例 3：
 *
 * 输入：root = [1,2], p = 1, q = 2
 * 输出：1
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [2, 105] 内
 */

//方法一 ：
public class BinaryTreeExercise1 {

    static class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
   }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }


        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);

        if(leftTree != null && rightTree != null) {
            return root;
        }else if(leftTree != null && rightTree == null) {
            return leftTree;
        }else {
            return rightTree;
        }


    }







    //最近公共祖先,方法二 ：
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {


        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        //1.把元素存入栈中
        getPath(root, p,stackP);
        getPath(root, q,stackQ);


        //2.求出那个栈元素多，让多的先出栈，直到两个栈元素一样多
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            //元素多的栈先走出栈，他们的差值元素个数
            while (size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }


        //看看栈顶元素，是否相等不相等就弹出，相等则就是最近祖先
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {

            //stackP == stackQ，比较节点，如果比较的值是Integer类型,超过一定范围就要无效，要用equals比较
            if ( stackQ.peek() == stackP.peek()) {
                return stackP.peek();
            }else {
                //元素不一样就出栈
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }


    /**
     *
     * @param root
     * @param node:要找路径的q p 节点
     * @param stack:存放节点的栈
     */
    //获取q, p路径
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        //节点放入栈中
        stack.push(root);

        //找到返回true
        if (root == node) {
            return true;
        }

        //递归找q, p, 递归返回值ret
        boolean ret = getPath(root.left,node,stack);
        //一层一层往上走
        if (ret) {
            return true;
        }

        ret = getPath(root.right,node,stack);
        if (ret) {
            return true;
        }

        //左右树遍历完没有找到,就把不是该路径的，节点弹出栈，并返回false
        stack.pop();
        return false;

    }
}
